package string;


import com.sun.xml.internal.bind.v2.model.core.ID;

import java.util.ArrayList;
import java.util.List;

/**
 * @author kaho
 * @since 2021/3/8
 */
public class _131_分割回文串 {

    /**给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

     回文串 是正着读和反着读都一样的字符串。
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> cur = new ArrayList<>();

        dfs(0, s, result, cur);
        return result;
    }

    private void dfs(int index, String s, List<List<String>> result, List<String> cur) {
        if (index == s.length()) {
            result.add(new ArrayList<>(cur));
            return;
        }

        for (int i = index; i < s.length(); i++) {
            if (isTure(s, index, i)){
                cur.add(new String(s.toCharArray(), index, i- index+1));
                dfs(i+1, s, result, cur);
                cur.remove(cur.size()-1);
            }
        }
    }

    private boolean isTure(String s, int index, int i) {
        while (i > index) {
            if (s.charAt(index)!=s.charAt(i)) {
                return false;
            }
            index++;
            i --;
        }
        return true;
    }
}
